#include "grate/util/compact_queue.h"

#include <sstream>
#include <string>
#include "grate/util/common.h"
#include "grate/util/word.h"

namespace growth_rate {

CompactQueue::CompactQueue(size_t capacity_in_bytes,
                           size_t item_size_in_bits)
    : capacity_in_bytes_(capacity_in_bytes),
      item_size_in_bits_(item_size_in_bits),
      num_of_items_(0),
      head_bit_pos_(0),
      tail_bit_pos_(0) {
  CHECK_GT(capacity_in_bytes_, 0);
  CHECK(1 <= item_size_in_bits_ && item_size_in_bits_ <= kBitsInByte);
  buffer_ = AllocateArray<uint8_t>(capacity_in_bytes_);
}

size_t CompactQueue::get_capacity_in_bytes() const {
  return capacity_in_bytes_;
}

size_t CompactQueue::get_capacity_in_items() const {
  CHECK_GT(item_size_in_bits_, 0);
  return capacity_in_bytes_ * kBitsInByte / item_size_in_bits_;
}

bool CompactQueue::is_empty() const {
  return num_of_items_ == 0;
}

size_t CompactQueue::get_size_in_bytes() const {
  size_t size_in_bits = num_of_items_ * item_size_in_bits_;
  return (size_in_bits + kBitsInByte - 1) / kBitsInByte;
}

size_t CompactQueue::get_size_in_items() const {
  return num_of_items_;
}

bool CompactQueue::push_item(uint8_t item) {
  if (num_of_items_ == get_capacity_in_items()) {
    return false;
  }
  put_item_at_bit_pos(item, tail_bit_pos_);
  shift_bit_pos(&tail_bit_pos_);
  num_of_items_++;
  return true;
}

size_t CompactQueue::push_word(const Word &word) {
  size_t n = word.length();
  for (size_t i = 0; i < n; i++) {
    if (!push_item(word[i])) {
      return i;
    }
  }
  return n;
}

uint8_t CompactQueue::peek_item() const {
  CHECK_GT(num_of_items_, 0);
  return get_item_at_bit_pos(head_bit_pos_);
}

uint8_t CompactQueue::pop_item() {
  CHECK_GT(num_of_items_, 0);
  uint8_t res = get_item_at_bit_pos(head_bit_pos_);
  shift_bit_pos(&head_bit_pos_);
  num_of_items_--;
  return res;
}

Word CompactQueue::pop_word(uint8_t *buffer, size_t length) {
  for (size_t i = 0; i < length; i++)
    buffer[i] = pop_item();
  return Word::createWordFromArray(buffer, length);
}

size_t CompactQueue::dump_to_array(uint8_t *array, size_t max_size) const {
  size_t items_to_dump = Min(num_of_items_, max_size);
  size_t item_bit_pos = head_bit_pos_;
  for (size_t i = 0; i < items_to_dump; i++) {
    array[i] = get_item_at_bit_pos(item_bit_pos);
    shift_bit_pos(&item_bit_pos);
  }
  return items_to_dump;
}

std::string CompactQueue::dump() const {
  std::stringstream out;
  out << "[";
  size_t item_bit_pos = head_bit_pos_;
  for (size_t i = 0; i < num_of_items_; i++) {
    uint8_t item = get_item_at_bit_pos(item_bit_pos);
    shift_bit_pos(&item_bit_pos);
    if (i > 0) out << ", ";
    out << static_cast<int>(item);
  }
  out << "]";
  return out.str();
}

void CompactQueue::shift_bit_pos(size_t *bit_pos) const {
  *bit_pos += item_size_in_bits_;
  *bit_pos %= (kBitsInByte * capacity_in_bytes_);
}

uint8_t CompactQueue::get_item_at_bit_pos(size_t bit_pos) const {
  CHECK(0 <= bit_pos && bit_pos < kBitsInByte * capacity_in_bytes_);
  uint8_t res = 0;
  uint8_t *byte = &buffer_[bit_pos / kBitsInByte];
  uint8_t byte_offset = static_cast<uint8_t>(bit_pos % kBitsInByte);
  uint8_t mask = (1 << item_size_in_bits_) - 1;
  res |= ((*byte) & (mask << byte_offset)) >> byte_offset;
  if (byte_offset + item_size_in_bits_ > kBitsInByte) {
    byte++;
    if (byte == buffer_ + capacity_in_bytes_) {
      byte = buffer_;
    }
    uint8_t bits_left = byte_offset + item_size_in_bits_ - kBitsInByte;
    mask = (1 << bits_left) - 1;
    res |= ((*byte) & mask) << (item_size_in_bits_ - bits_left);
  }
  return res;
}

void CompactQueue::put_item_at_bit_pos(uint8_t item, size_t bit_pos) {
  CHECK(item < (1 << item_size_in_bits_));
  uint8_t *byte = &buffer_[bit_pos / kBitsInByte];
  uint8_t byte_offset = static_cast<uint8_t>(bit_pos % kBitsInByte);
  uint8_t mask = (1 << item_size_in_bits_) - 1;
  *byte &= ~(mask << byte_offset);
  *byte |= (item << byte_offset);
  if (byte_offset + item_size_in_bits_ > kBitsInByte) {
    byte++;
    if (byte == buffer_ + capacity_in_bytes_) {
      byte = buffer_;
    }
    uint8_t bits_left = byte_offset + item_size_in_bits_ - kBitsInByte;
    *byte &= ~((1 << bits_left) - 1);
    *byte |= (item >> (item_size_in_bits_ - bits_left));
  }
}

Word IncreasingLengthWordQueue::pop_word(uint8_t *buffer, size_t buffer_size) {
  CHECK_GT(shorter_words_, 0);
  if (buffer_size < word_length_)
    return Word();
  Word word = queue_.pop_word(buffer, word_length_);
  DCHECK_EQ(word_length_, word.length());
  shorter_words_--;
  if (shorter_words_ == 0) {
    shorter_words_ = longer_words_;
    longer_words_ = 0;
    word_length_++;
  }
  return word;
}

void IncreasingLengthWordQueue::push_word(const Word &word) {
  if (longer_words_ > 0) {
    CHECK_EQ(word_length_ + 1, word.length());
    longer_words_++;
  } else if (shorter_words_ > 0) {
    CHECK_LE(word_length_, word.length());
    CHECK_LE(word.length(), word_length_ + 1);
    if (word_length_ == word.length())
      shorter_words_++;
    else
      longer_words_++;
  } else {
    shorter_words_ = 1;
    word_length_ = word.length();
  }
  CHECK_EQ(word.length(), queue_.push_word(word));
}

}  // namespace growth_rate
